package com.roy.galaxy.algorithm;

import com.google.common.collect.Maps;
import org.apache.commons.lang3.StringUtils;

import java.util.HashMap;
import java.util.Map;

/**
 * @author gang.wang1903@xiaobao100.cn
 * @Date: 2019-10-18 09:37
 */
public class 最长子串 {


    /**
     * 时间复杂度O(n^2) 空间复杂度O(1)
     * 时间复杂度太高，需要优化
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {

        Integer max = 0;
        if(s == null || s.length() == 0){

            return max;
        }
        if(s.length() == 1){

            return 1;
        }
        for(int i = 0 ; i < s.length()-1 ; i++){

            HashMap map = new HashMap();
            Integer temp = 0;

            for(int j = i ; j < s.length()-1 ; j ++ ){
               map.put( s.charAt(j),s.charAt(j));
               if(map.containsKey(s.charAt(j+1))){
                   temp = map.entrySet().size();
                   if(temp > max){
                       max = temp;
                   }
                   break;
               }else {
                   temp =  map.entrySet().size() + 1;
                   if(temp > max){
                       max = temp;
                   }
               }
            }
        }
        return max;
    }

    /**
     * 滑动窗口
     * 时间复杂度o(n)，空间复杂度o(n)
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring2(String s) {

        int n = s.length();
        int ans = 0;
        Map<Character,Integer> map = new HashMap<>();
        for(int start = 0 ,end = 0 ; end < n ; end ++){
            char alpha = s.charAt(end);
            if(map.containsKey(alpha)){
                start = Math.max(map.get(alpha), start);
            }else {
                map.put(s.charAt(end), end + 1);
                ans = Math.max(ans, end - start + 1);
            }
        }
        return ans;
    }


    public static void main(String[] args) {
       System.out.print( new 最长子串().lengthOfLongestSubstring2("dvdf"));
    }

}
